package gold.digger;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC126 {
    public long startExecuteTime = System.currentTimeMillis();

//    输入:
//    beginWord = "hit",
//    endWord = "cog",
//    wordList = ["hot","dot","dog","lot","log","cog"]
//
//    输出:
//            [
//            ["hit","hot","dot","dog","cog"],
//              ["hit","hot","lot","log","cog"]
//            ]

    /*
     * @param 此题目参考了别人代码
     * 这是因为问题情况较为复杂
     * 可以借鉴思想，多多学习
     * @return:
     */
    class Solution {
        private static final int INF = 1 << 20;
        private Map<String, Integer> wordId; // 单词到id的映射
        private ArrayList<String> idWord; // id到单词的映射
        private ArrayList<Integer>[] edges; // 图的边

        public Solution() {
            wordId = new HashMap<>();
            idWord = new ArrayList<>();
        }

        public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
            int id = 0;
            // 将wordList所有单词加入wordId中 相同的只保留一个 // 并为每一个单词分配一个id
            for (String word : wordList) {
                if (!wordId.containsKey(word)) {
                    wordId.put(word, id++);
                    idWord.add(word);
                }
            }
            // 若endWord不在wordList中 则无解
            if (!wordId.containsKey(endWord)) {
                return new ArrayList<>();
            }
            // 把beginWord也加入wordId中
            if (!wordId.containsKey(beginWord)) {
                wordId.put(beginWord, id++);
                idWord.add(beginWord);
            }

            // 初始化存边用的数组
            edges = new ArrayList[idWord.size()];
            for (int i = 0; i < idWord.size(); i++) {
                edges[i] = new ArrayList<>();
            }
            // 添加边
            for (int i = 0; i < idWord.size(); i++) {
                for (int j = i + 1; j < idWord.size(); j++) {
                    // 若两者可以通过转换得到 则在它们间建一条无向边
                    if (transformCheck(idWord.get(i), idWord.get(j))) {
                        edges[i].add(j);
                        edges[j].add(i);
                    }
                }
            }

            int dest = wordId.get(endWord); // 目的ID
            List<List<String>> res = new ArrayList<>(); // 存答案
            int[] cost = new int[id]; // 到每个点的代价
            for (int i = 0; i < id; i++) {
                cost[i] = INF; // 每个点的代价初始化为无穷大
            }

            // 将起点加入队列 并将其cost设为0
            Queue<ArrayList<Integer>> q = new LinkedList<>();
            ArrayList<Integer> tmpBegin = new ArrayList<>();
            tmpBegin.add(wordId.get(beginWord));
            q.add(tmpBegin);
            cost[wordId.get(beginWord)] = 0;

            // 开始广度优先搜索
            while (!q.isEmpty()) {
                ArrayList<Integer> now = q.poll();
                int last = now.get(now.size() - 1); // 最近访问的点
                if (last == dest) { // 若该点为终点则将其存入答案res中
                    ArrayList<String> tmp = new ArrayList<>();
                    for (int index : now) {
                        tmp.add(idWord.get(index)); // 转换为对应的word
                    }
                    res.add(tmp);
                } else { // 该点不为终点 继续搜索
                    for (int i = 0; i < edges[last].size(); i++) {
                        int to = edges[last].get(i);
                        // 此处<=目的在于把代价相同的不同路径全部保留下来
                        if (cost[last] + 1 <= cost[to]) {
                            cost[to] = cost[last] + 1;
                            // 把to加入路径中
                            ArrayList<Integer> tmp = new ArrayList<>(now);
                            tmp.add(to);
                            q.add(tmp); // 把这个路径加入队列
                        }
                    }
                }
            }
            return res;
        }

        // 两个字符串是否可以通过改变一个字母后相等
        boolean transformCheck(String str1, String str2) {
            int differences = 0;
            for (int i = 0; i < str1.length() && differences < 2; i++) {
                if (str1.charAt(i) != str2.charAt(i)) {
                    ++differences;
                }
            }
            return differences == 1;
        }
    }


    class Solution_Time_Exceed {

        public Set<String> dict = new HashSet<>();
        public List<List<String>> res = new ArrayList<>();
        public int minPathLength = Integer.MAX_VALUE;

        public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
            for (String word : wordList) dict.add(word);
            if (!dict.contains(endWord)) return res;

            char[] curProcessWordArray = new char[beginWord.length()];
            for (int i = 0; i < beginWord.length(); i++) {
                curProcessWordArray[i] = beginWord.charAt(i);
            }

            List<String> curPathSet = new LinkedList<>();
            findLaddersBFS(curProcessWordArray, endWord, curPathSet);

            List<List<String>> minLengthRes = new ArrayList<>();
            for (List<String> re : res) {
                if (re.size() == minPathLength) minLengthRes.add(re);
            }
            return minLengthRes;
        }

        public void findLaddersBFS(char[] curProcessWordArray, String endWord,
                                   List<String> curPath) {
            String curWord = new String(curProcessWordArray);
            if (curWord.equals(endWord)) {
                List<String> findPath = copyList(curPath);
                findPath.add(endWord);
                if (findPath.size() < minPathLength) minPathLength = findPath.size();
                res.add(findPath);
                return;
            }

            if (curPath.contains(curWord)) return;

            curPath.add(curWord);
            for (int j = 0; j < curProcessWordArray.length; j++) {
                for (int i = 0; i < 26; i++) {
                    char curPosChar = curProcessWordArray[j];
                    curProcessWordArray[j] = (char) ('a' + i);
                    curWord = new String(curProcessWordArray);
                    if (!dict.contains(curWord)) {
                        curProcessWordArray[j] = curPosChar;
                        continue;
                    }

                    findLaddersBFS(curProcessWordArray, endWord, curPath);
                    curProcessWordArray[j] = curPosChar;
                }
            }
            curPath.remove(curPath.size() - 1);
        }

        public List<String> copyList(List<String> curPath) {
            List<String> copyList = new LinkedList<>();
            for (String node : curPath) {
                copyList.add(new String(node));
            }
            return copyList;
        }

    }

    public void run() {
        Solution solution = new Solution();
        String[] wordList = {"hot", "dot", "dog", "lot", "log", "cog"};
        System.out.println(solution.findLadders("hit", "cog", Arrays.asList(wordList)));
    }

    public static void main(String[] args) throws Exception {
        LC126 an = new LC126();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
